<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Median of Two Sorted Arrays</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="median-of-two-sorted-arrays">Median of Two Sorted Arrays</h1>
<ul>
<li><a href="https://leetcode.com/problems/median-of-two-sorted-arrays/">https://leetcode.com/problems/median-of-two-sorted-arrays/</a></li>
</ul>
<h2 id="1这道算法题太简单你忽略了时间复杂度的要求">(1)这道算法题太简单？你忽略了时间复杂度的要求！</h2>
<p><a href="https://blog.csdn.net/kexuanxiu1163/article/details/98913301">https://blog.csdn.net/kexuanxiu1163/article/details/98913301</a></p>
<p>感觉这种算法比下面 小灰的算法要更容易理解一些</p>
<h2 id="2-程序员小灰">(2) 程序员小灰</h2>
<p><a href="http://www.sohu.com/a/330041682_684445">http://www.sohu.com/a/330041682_684445</a></p>
<h2 id="3-tushar-roy-解法最好理解-和2一样">(3) tushar roy 解法最好理解, 和(2)一样</h2>
<ul>
<li><a href="https://www.youtube.com/watch?v=LPFhl65R7ww">https://www.youtube.com/watch?v=LPFhl65R7ww</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/binarysearch/MedianOfTwoSortedArrayOfDifferentLength.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/binarysearch/MedianOfTwoSortedArrayOfDifferentLength.java</a></li>
</ul>
<p>tushare roy的代码</p>
<pre><code class="language-java"><div><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MedianOfTwoSortedArrayOfDifferentLength</span> </span>{

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">double</span> <span class="hljs-title">findMedianSortedArrays</span><span class="hljs-params">(<span class="hljs-keyword">int</span> input1[], <span class="hljs-keyword">int</span> input2[])</span> </span>{
        <span class="hljs-comment">//if input1 length is greater than switch them so that input1 is smaller than input2.</span>
        <span class="hljs-keyword">if</span> (input1.length &gt; input2.length) {
            <span class="hljs-keyword">return</span> findMedianSortedArrays(input2, input1);
        }
        <span class="hljs-keyword">int</span> x = input1.length;
        <span class="hljs-keyword">int</span> y = input2.length;

        <span class="hljs-keyword">int</span> low = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">int</span> high = x;
        <span class="hljs-keyword">while</span> (low &lt;= high) {
            <span class="hljs-keyword">int</span> partitionX = (low + high)/<span class="hljs-number">2</span>;
            <span class="hljs-keyword">int</span> partitionY = (x + y + <span class="hljs-number">1</span>)/<span class="hljs-number">2</span> - partitionX;

            <span class="hljs-comment">//if partitionX is 0 it means nothing is there on left side. Use -INF for maxLeftX</span>
            <span class="hljs-comment">//if partitionX is length of input then there is nothing on right side. Use +INF for minRightX</span>
            <span class="hljs-keyword">int</span> maxLeftX = (partitionX == <span class="hljs-number">0</span>) ? Integer.MIN_VALUE : input1[partitionX - <span class="hljs-number">1</span>];
            <span class="hljs-keyword">int</span> minRightX = (partitionX == x) ? Integer.MAX_VALUE : input1[partitionX];

            <span class="hljs-keyword">int</span> maxLeftY = (partitionY == <span class="hljs-number">0</span>) ? Integer.MIN_VALUE : input2[partitionY - <span class="hljs-number">1</span>];
            <span class="hljs-keyword">int</span> minRightY = (partitionY == y) ? Integer.MAX_VALUE : input2[partitionY];

            <span class="hljs-keyword">if</span> (maxLeftX &lt;= minRightY &amp;&amp; maxLeftY &lt;= minRightX) {
                <span class="hljs-comment">//We have partitioned array at correct place</span>
                <span class="hljs-comment">// Now get max of left elements and min of right elements to get the median in case of even length combined array size</span>
                <span class="hljs-comment">// or get max of left for odd length combined array size.</span>
                <span class="hljs-keyword">if</span> ((x + y) % <span class="hljs-number">2</span> == <span class="hljs-number">0</span>) {
                    <span class="hljs-keyword">return</span> ((<span class="hljs-keyword">double</span>)Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY))/<span class="hljs-number">2</span>;
                } <span class="hljs-keyword">else</span> {
                    <span class="hljs-keyword">return</span> (<span class="hljs-keyword">double</span>)Math.max(maxLeftX, maxLeftY);
                }
            } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (maxLeftX &gt; minRightY) { <span class="hljs-comment">//we are too far on right side for partitionX. Go on left side.</span>
                high = partitionX - <span class="hljs-number">1</span>;
            } <span class="hljs-keyword">else</span> { <span class="hljs-comment">//we are too far on left side for partitionX. Go on right side.</span>
                low = partitionX + <span class="hljs-number">1</span>;
            }
        }

        <span class="hljs-comment">//Only we we can come here is if input arrays were not sorted. Throw in that scenario.</span>
        <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> IllegalArgumentException();
    }

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>{
        <span class="hljs-keyword">int</span>[] x = {<span class="hljs-number">1</span>, <span class="hljs-number">3</span>, <span class="hljs-number">8</span>, <span class="hljs-number">9</span>, <span class="hljs-number">15</span>};
        <span class="hljs-keyword">int</span>[] y = {<span class="hljs-number">7</span>, <span class="hljs-number">11</span>, <span class="hljs-number">19</span>, <span class="hljs-number">21</span>, <span class="hljs-number">18</span>, <span class="hljs-number">25</span>};

        MedianOfTwoSortedArrayOfDifferentLength mm = <span class="hljs-keyword">new</span> MedianOfTwoSortedArrayOfDifferentLength();
        mm.findMedianSortedArrays(x, y);
    }
}
</div></code></pre>
<p>我的代码</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findMedianSortedArrays</span><span class="hljs-params">(self, nums1: List[int], nums2: List[int])</span> -&gt; float:</span>
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_helper</span><span class="hljs-params">(nums1, nums2)</span>:</span>
            m = len(nums1)
            n = len(nums2)
            <span class="hljs-keyword">if</span> m &gt; n:
                <span class="hljs-keyword">return</span> _helper(nums2, nums1)
            
            left = <span class="hljs-number">0</span> 
            right = m
            <span class="hljs-keyword">while</span> left &lt;= right:
                mid1 = (left + right) // <span class="hljs-number">2</span>
                mid2 = (m + n + <span class="hljs-number">1</span>) // <span class="hljs-number">2</span> - mid1
                    
                left_max_1 = -float(<span class="hljs-string">'inf'</span>) <span class="hljs-keyword">if</span> mid1 == <span class="hljs-number">0</span> <span class="hljs-keyword">else</span> nums1[mid1<span class="hljs-number">-1</span>]
                right_min_1 = float(<span class="hljs-string">'inf'</span>) <span class="hljs-keyword">if</span> mid1 == m <span class="hljs-keyword">else</span> nums1[mid1]
                
                left_max_2 = -float(<span class="hljs-string">'inf'</span>) <span class="hljs-keyword">if</span> mid2 == <span class="hljs-number">0</span> <span class="hljs-keyword">else</span> nums2[mid2<span class="hljs-number">-1</span>]
                right_min_2 = float(<span class="hljs-string">'inf'</span>) <span class="hljs-keyword">if</span> mid2 == n <span class="hljs-keyword">else</span> nums2[mid2]
                
                <span class="hljs-comment">#print(f"{mid1} {mid2} {left_max_1} {right_min_1} {left_max_2} {right_min_2}" )</span>
                <span class="hljs-keyword">if</span> left_max_1 &lt;= right_min_2 <span class="hljs-keyword">and</span> left_max_2 &lt;= right_min_1:
                    <span class="hljs-keyword">if</span> (m+n) % <span class="hljs-number">2</span> == <span class="hljs-number">0</span>:
                        <span class="hljs-keyword">return</span> (max(left_max_1, left_max_2) + min(right_min_1, right_min_2)) / <span class="hljs-number">2</span>
                    <span class="hljs-keyword">else</span>:
                        <span class="hljs-keyword">return</span> max(left_max_1, left_max_2)
                <span class="hljs-keyword">elif</span> left_max_1 &gt; right_min_2:
                    right = mid1
                <span class="hljs-keyword">else</span>:
                    left = mid1 + <span class="hljs-number">1</span>
            <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
                    
        <span class="hljs-keyword">return</span> _helper(nums1, nums2)
    
    
</div></code></pre>

    </body>
    </html>